package study.datastructure.tree;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-06-04 23:00
 * @auther teacher
 * @date 2024/6/4
 * @project datastructure
 * @auther teacher
 * @date 2024/6/4
 * @project datastructure
 */

/**
 @auther teacher
 @date 2024/6/4
 @project datastructure
 */

import java.sql.PreparedStatement;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description: 二叉树
 */
public class BinaryTree {
    TreeNode root;

    public void insert(int value) {
        root = insertRec(root, value);
    }

    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) {
            root = new TreeNode(value);
            return root;
        }

        if (value < root.val) {
            root.left = insertRec(root.left, value);
        } else if (value > root.val) {
            root.right = insertRec(root.right, value);
        }
        return root;
    }

    // region 递归遍历
    //中序遍历
    public static void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        preorderTraversal(root.left);
        System.out.print(root.val + " ");
        preorderTraversal(root.right);
    }

    //前序遍历
    public static void preorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);

    }

    //后序遍历
    public static void endOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        System.out.print(root.val + " ");
    }
//endregion

    /**
     * leetcode101 检查二叉树是否对称
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        return check(root.left, root.right);

    }

    private boolean check(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        //左右子树不能同时为空
        if (right == null || left == null) {
            return false;
        }

        if (left.val != right.val) {
            return false;
        }

        return check(left.left, right.right) && check(left.right, right.left);

    }

    /**
     * leetcode104 计算树的最大深度
     * 计算思路 左子树深度 右子树深度 取最大值+1
     * 后序遍历（DFS）
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //if (root.left==null&&root.right==null) return 1;

        int d1 = maxDepth(root.left);
        int d2 = maxDepth(root.right);
        return Integer.max(d1, d2) + 1;
    }

    /**
     * 后序 栈
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root, boolean b) {
        TreeNode curr = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode pop = null;
        int maxDepth = 0; //计算最大深度

        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                int size = stack.size();
                if (size > maxDepth) {
                    maxDepth = size;
                }
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop) {
                    pop = stack.pop();
                } else {
                    curr = peek.right;
                }
            }

        }
        return maxDepth;
    }

    /**
     * 层序
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root, long a) {
        if (root == null) return 0;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>() {{
            add(root);
        }}, tmp;
        int res = 0;

        while (!queue.isEmpty()) {
            tmp = new LinkedList<>();
            for (TreeNode node : queue) {
                if (node.left != null) tmp.add((node.left));
                if (node.right != null) tmp.add((node.right));
            }
            queue = tmp;
            res++;
        }
        return res;
    }

    /**
     * leetcode111 计算树的最小深度
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //这道题递归条件里分为三种情况
        //1.左孩子和有孩子都为空的情况，说明到达了叶子节点，直接返回1即可

        int m1 = minDepth(root.left);
        int m2 = minDepth(root.right);
        //2.如果左孩子和由孩子其中一个为空，那么需要返回比较大的那个孩子的深度
        //这里其中一个节点为空，说明m1和m2有一个必然为0，所以可以返回m1 + m2 + 1;

        //3.最后一种情况，也就是左右孩子都不为空，返回最小深度+1即可

        //这里做了简化  //1.如果左孩子和右孩x子有为空的情况，直接返回m1+m2+1
        //        //2.如果都不为空，返回较小深度+1
        return (root.left == null || root.right == null) ? m1 + m2 + 1 : Integer.min(m1, m2) + 1;
    }

    /**
     * leetcode226 翻转二叉树
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode tmp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(tmp);
        return root;
    }

    /**
     * leetcode105 根据前序和中序遍历构建二叉树
     * @param preorder
     * @param inorder
     * @return
     */
    int[] preorder;
    HashMap<Integer, Integer> dic = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            dic.put((inorder[i]), i);
        }
        return recur(0, 0, inorder.length - 1);
    }

    /**
     * 递推参数：
     * @param root 根节点在前序遍历的索引 root
     * @param left 子树在中序遍历的左边界 left
     * @param right 子树在中序遍历的右边界 right 。
     * @return
     */
    private TreeNode recur(int root, int left, int right) {
        //递归终止
        if (left > right) return null;
        //建立根节点
        TreeNode node = new TreeNode(preorder[root]);
        //划分根节点 左子树 右子树
        int i = dic.get(preorder[root]); //在中序遍历中找到根节点的位置
        //开启左子树递归
        node.left = recur(root + 1, left, i - 1);
        //开启右子树递归
        node.right = recur(root + i - left + 1, i + 1, right); //根节点+左子树长度=右子树根节点
        //回溯返回根节点
        return node;

    }

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.insert(5);
        binaryTree.insert(7);
        binaryTree.insert(10);
        binaryTree.insert(2);
        binaryTree.insert(1);
        binaryTree.insert(9);
        //inorderTraversal(binaryTree.root);
        // endOrderTraversal(binaryTree.root);
        //preorderTraversal(binaryTree.root);

        TreeNode root = binaryTree.root;
        TreeNode curr = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
/*
        //非递归 路径相同 前序 中序
        while (curr!=null||!stack.isEmpty()){
            if (curr!=null){
                System.out.println("去"+curr.val); //前序
                stack.push(curr);
                curr=curr.left;
            }else {
                TreeNode pop = stack.pop();
                System.out.println("stack.pop().val = " + pop.val); //中序
                curr=pop.right;
            }
        } */
       /* //非递归 路径相同 后序
        TreeNode pop=null;
        while (curr!=null||!stack.isEmpty()){
            if (curr!=null){
                System.out.println("去"+curr.val);
                stack.push(curr);
                // 待处理左子树
                curr=curr.left;
            }else {
                TreeNode peek = stack.peek();
                if(peek.right==null||peek.right==pop){
                    pop=stack.pop();
                    System.out.println("stack.pop().val = " + pop.val);
                }  else {
                    curr=peek.right;
                }
            }
        } */
        //非递归 路径相同
        List<Integer> result = new ArrayList<Integer>();
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                colorPrint(curr.val, "blue"); //前序
                stack.push(curr);
                // 待处理左子树
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                // 右子树为空
                if (peek.right == null) {
                    colorPrint(peek.val, "red"); //中序
                    pop = stack.pop();
                    colorPrint(pop.val, "green");//后序
                }
                // 右子树已处理
                else if (peek.right == pop) {
                    pop = stack.pop();
                    colorPrint(pop.val, "green");//green
                }
                // 右子树待处理
                else {
                    colorPrint(peek.val, "red");//中序
                    curr = peek.right;
                }
            }
        }
    }

    private static void colorPrint(int value, String color) {
        switch (color) {
            case "red": //中序
                System.out.printf("\033[0;31m%d\033[0m ", value); // 红色
                break;
            case "blue": //前序
                System.out.printf("\033[0;34m%d\033[0m ", value); // 蓝色
                break;
            case "green": //后序
                System.out.printf("\033[0;32m%d\033[0m ", value); // 绿色
                break;
            default:
                System.out.print(value + " ");
                break;
        }
    }
}
